package com.aqie.arithmetic.datastructure;

/**
 * 基于线性探测的符号表
 * @param <Key>
 * @param <Value>
 */
public class LinearProbingHashST<Key, Value> {
    // 符号表中键值对的总数
    private int N;

    // 线性探测表的大小
    private int M = 16;

    // 键
    private Key[] keys;

    // 值
    private Value[] values;

    public LinearProbingHashST(){
        keys = (Key[]) new Object[M];
        values = (Value[]) new Object[M];
    }

    public LinearProbingHashST(int M){
        this.M = M;
        keys = (Key[]) new Object[M];
        values = (Value[]) new Object[M];
    }

    private int hash(Key key){
        return (key.hashCode() & 0x7fffffff) % M;
    }

    private void resize(){
        // 3.4.4
    }

    public void put(Key key, Value value){
        if (N >= M / 2) resize(2 * M);
        int i;
        for (i = hash(key); keys[i] != null; i = (i + 1) % M){
            if (keys[i].equals(key)){
                values[i] = value; return;
            }
        }
        keys[i] = key;
        values[i] = value;
        N++;
    }

    public Value get(Key key){
        for (int i = hash(key); keys[i] != null; i = (i + 1) % M){
            if (keys[i].equals(key)){
                return values[i];
            }
        }
        return null;
    }



    public void delete(Key key){
        if (!contains(key)) return;
        int i = hash(key);
        while (!key.equals(keys[i])){
            i = (i + 1) % M;
        }
        keys[i] = null;
        values[i] = null;
        i = (i + 1) % M;
        while (keys[i] != null){
            Key keyToRedo = keys[i];
            Value valToRedo = values[i];
            keys[i] = null;
            values[i] = null;
            N--;
            put(keyToRedo, valToRedo);
            i = (i + 1) % M;
        }
        N--;
        if (N > 0 && N == M / 8) resize(M / 2);
    }

    // todo 优化
    private boolean contains(Key key) {
        for (int i= 0; i < N ; i++){
            if (keys[i] == key) return true;
        }
        return false;
    }

    private void resize(int cap){
        LinearProbingHashST<Key, Value> t;
        t = new LinearProbingHashST<>(cap);
        for (int i = 0; i < M; i++){
            if (keys[i] != null){
                t.put(keys[i], values[i]);
            }
        }
        keys = t.keys;
        values = t.values;
        M = t.M;
    }
}
